package 题目集.单调栈or队列.单调栈;

import org.junit.Test;

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * https://leetcode.cn/problems/maximal-rectangle/description/
 */
public class 最大矩阵 {
    /**
     *  暴力：
     *      先求二维前缀和。然后枚举每一个左下角点，和他对应的右上角点，判断是否是矩形。
     *      时间复杂度：O(n^4)
     *
     *  单调栈解：
     *      1.将每一列看成一个柱状图，然后求出每一行的最大矩形面积。
     *      2.枚举每一个高度下的最大矩形面积。
     *      时间复杂度：O(n^2)
     */
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] heights = new int[m]; //每一列的高度

        int[] left = new int[m];
        int[] right = new int[m];
        int[] stack = new int[m];
        int top = -1;
        int res = 0;
        for (int i = 0; i < n; i++) {
            //求出每一列的高度
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {  //这一行和之前的柱状图能连上
                    heights[j]++;
                } else {
                    heights[j] = 0; //这一行和之前的柱状图断开
                }
            }
            for (int j = 0; j < heights.length; j++) {
                while (top != -1 && heights[j] <= heights[stack[top]]) {
                    right[stack[top--]] = j;
                }
                if (top != -1) {
                    left[j] = stack[top];
                }else {
                    left[j]=-1; //左侧没有了
                }
                stack[++top] = j;
            }
            while (top != -1) {
                right[stack[top--]] = m;
            }
            for (int j = 0; j < heights.length; j++) {
                int area = heights[j] * (right[j] - left[j] - 1);   //-1是因为不包含左右边界
                res = Math.max(res, area);
            }
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(maximalRectangle(new char[][]{{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}}));
    }
}
